/*Date-11-08-11
 *The following code solves the famous queens problem,which asks for a 
 *configuration of 8 queens on a chess board in such a way that none of them can   
 *capture each other.The method is generalized,and uses backtracking.
 *Authored by Sarvesh Iyer
 */

import scala.collection.mutable._
//taking the coordinates of two queens,returns whether they can capture each 
//other.
def canCapture(tup1:(Int,Int),tup2:(Int,Int)):Boolean= {
    if(tup1._1==tup2._1||tup1._2==tup2._2) {//queens are in same row or column
        return true
    }
    else if(Math.abs(tup1._1-tup2._1)==Math.abs(tup1._2-tup2._2)) {//queens lie 
        //along same diagonal
        return true
    }
    else return false
}
//finds a character in a given String
def find(s:Char,a:StringBuilder):Int= {
    for(i<-0 until a.length) {
        if(a.charAt(i)==s) {
            return i
        }
    }
    return -1
}    
//The main function,generating the combination of queens that solves the 
//problem    
def UncapturableQueenFormation(const:Int):Unit= {  
    var dda=new Array[StringBuilder](const)
    for(i<-0 to const-1) {
        dda(i)=new StringBuilder(const)
        for(j<-0 to const-1) {
            dda(i)+='/'  //initializing squares
        }
    }
    var iter=0
    while (iter<=const-1) {
        var iter2=find('Q',dda(iter))
        if(iter2==(-1)) iter2=0
        dda(iter)(iter2)='Q'//initializing position of queen
        if(findSuitablePlace(iter2,const,iter,dda)!=(-1)) {
            //changing the queen to a suitable position
            swapIndices(dda(iter),iter2,findSuitablePlace(iter2,const,iter,dda))
            iter+=1
        }                
        else {
            iter-=1
        }
    }
    for(i<-0 to const-1) {
         print(dda(i))//printing board out.
    }
}
//changes the position of two characters in a string
def swapIndices(a:StringBuilder,b:Int,c:Int) ={
    var t=a.charAt(b)
    a(b)=a(c)
    a(c)=t
}
//finds the next position of a queen in a given row,such that she can not be 
//captured by any other queen.If not possible,it removes her from the board
def findSuitablePlace(a:Int,const:Int,iter:Int,dda:Array[StringBuilder]):Int= {
    var c=0
    if(a!=0) c=a+1
    var count=0
    while(c<=const-1) {
        for(i<-0 to const-1;j<-0 to const-1) {
            if(dda(i).charAt(j)=='Q' && i!=iter) { //is there a queen which is not
                //in the row being considered?
                if(canCapture((i,j),(iter,c))) {//can the queen be captured?
                    count+=1
                }
            }
        }
        if(count!=0) {//some queen could have captured it.
            c+=1
        }
        else {
            return c//position found.
        }
        count=0
    }
    dda(iter)(a)='/' //removing queen
    return -1
}
UncapturableQueenFormation(20) //calling method




